#include <algorithm>
#include <array>
#include <list>
#include <memory>
#include <iostream>
#include <vector>

using namespace std;

/**
 * @brief 桶排序
 * 1.建立数组
 * 2.建立数组中的链表
 * 3.将待排序数组元素放进通
 * 4.给每个桶的元素排序
 * 5.把所有桶中的元素合并，放回元素组
 *
 * @param vec　要排序的数组
 *
 * 注意桶中分配数据的方法为bucket.at(ele / bucket_num).push_back(ele);
 * 因此待排序数组最大值不能超过99，否则将超出桶的范围
 */
void bucket_sort(vector<int>& vec)
{
    //桶的数量
    const int bucket_num = 10;
    //1.建立数组
    //2.建立数组中的链表
    vector<list<int>> bucket(bucket_num);

    //3.将待排序数组元素放进通
    for (auto ele : vec) {
        bucket.at(ele / bucket_num).push_back(ele);
    }

    //4.给每个桶的元素排序
    for (auto &ele : bucket) {
        ele.sort();
    }

    //5.把所有桶中的元素合并，放回元素组
    vec.clear();
    for (auto& ele : bucket) {
        for (auto &i : ele) {
            vec.push_back(i);
        }
    }
}

int main(void)
{
    vector<int> vec{1, 3, 5, 23, 3, 5, 7, 8, 44, 68, 9, 35, 23, 6, 7};
    bucket_sort(vec);
    for (auto i : vec) {
        std::cout << i << std::endl;
    }
    return 0;
}
